import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;

public class Main {
    public int minimumRefill(int[] plants, int capacityA, int capacityB) {
        //方便后面重新装水
        int initA = capacityA;
        int initB =capacityB;
        int left = 0;
        int right = plants.length-1;
        int count = 0;
        while(left < right){
            if(capacityA < plants[left]){
                capacityA = initA;
                count++;
            }
            if(capacityB < plants[right]){
                capacityB = initB;
                count++;
            }
            capacityA = capacityA - plants[left];
            capacityB = capacityB - plants[right];
            left++;
            right--;
        }
        if(left == right && Math.max(capacityA,capacityB) < plants[left]){
            count++;
        }
        return count;
    }
/*
287. 寻找重复数
 */
    public int findDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0;i<nums.length;i++){
            if(set.contains(nums[i])){
                return nums[i];
            }else{
                set.add(nums[i]);
            }
        }
        return -1;
    }

/*
189. 轮转数组
 */
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        reverse(nums,0,nums.length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,nums.length-1);

    }
    public void reverse(int[] nums,int left,int right){
        while(left < right){
            int t = nums[left];
            nums[left] = nums[right];
            nums[right] = t;
            left++;
            right--;
        }
    }
    public int[][] merge(int[][] intervals) {
        if(intervals.length == 0){
            return new int[0][2];
        }
        //按照左边界排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        //存放最终合并的结果
        int[][] mergeAns = new int[intervals.length][2];

        int start = intervals[0][0];//存放左边界值
        int end = intervals[0][1];//存放右边界值
        for (int i = 1; i < intervals.length; i++) {
            //如果当前左边界值大于上一个区间的右边界值
            //说明不是一个区间内的，不可以合并
            if (intervals[i][0] >end){
                start = intervals[i][1];
                end = intervals[i][0];
            }
        }
        return mergeAns;
    }
}
